package com.sheng.leetcode.year2022.month10.day18;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/10/18
 *<p>
 * 902. 最大为 N 的数字组合<p>
 *<p>
 * 给定一个按 非递减顺序 排列的数字数组 digits 。<p>
 * 你可以用任意次数 digits[i] 来写的数字。<p>
 * 例如，如果 digits = ['1','3','5']，我们可以写数字，如 '13', '551', 和 '1351315'。<p>
 * 返回 可以生成的小于或等于给定整数 n 的正整数的个数 。<p>
 *<p>
 * 示例 1：<p>
 * 输入：digits = ["1","3","5","7"], n = 100<p>
 * 输出：20<p>
 * 解释：<p>
 * 可写出的 20 个数字是：<p>
 * 1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.<p>
 *<p>
 * 示例 2：<p>
 * 输入：digits = ["1","4","9"], n = 1000000000<p>
 * 输出：29523<p>
 * 解释：<p>
 * 我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，<p>
 * 81 个四位数字，243 个五位数字，729 个六位数字，<p>
 * 2187 个七位数字，6561 个八位数字和 19683 个九位数字。<p>
 * 总共，可以使用D中的数字写出 29523 个整数。<p>
 *<p>
 * 示例 3:<p>
 * 输入：digits = ["7"], n = 8<p>
 * 输出：1<p>
 *<p>
 * 提示：<p>
 * 1 <= digits.length <= 9<p>
 * digits[i].length == 1<p>
 * digits[i] 是从 '1' 到 '9' 的数<p>
 * digits 中的所有值都 不同<p>
 * digits 按 非递减顺序 排列<p>
 * 1 <= n <= 10^9<p>
 */
public class LeetCode0902 {

    @Test
    public void test01() {
//        String[] digits = {"1","3","5","7"};
//        int n = 100;
//        String[] digits = {"1","4","9"};
//        int n = 1000000000;
//        String[] digits = {"7"};
//        int n = 8;
//        String[] digits = {"1","4","7"};
//        int n = 154;
//        String[] digits = {"3","4","8"};
//        int n = 4;
        String[] digits = {"3","4","5","6"};
        int n = 64;
        System.out.println(new Solution().atMostNGivenDigitSet(digits, n));
    }
}
class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        int length = digits.length;
        int count = 0;
        int num = 10;
        int x = 1;
        // 计算能获取的比 n 位数小的，所有的组合方式
        while (n >= num) {
            int y = 1;
            for (int i = 0; i < x; i++) {
                y *= length;
            }
            count += y;
            num *= 10;
            x++;
        }
        // 计算和 n 位数相同的所有的组合方式
        String str = String.valueOf(n);
        boolean flag = true;
        for (int i = 0; i < str.length() && flag; i++) {
            // 如果存在相等字符，则比较下一个字符，如果到达 i 位置没有相等的字符时，计算数组 digits 中字符小余 i 位置的字符的数量，然后根据后续还有的位数进行循环，每次循环乘以数组 digits 的长度 length
            if (flag) {
                for (int j = 0; j < length; j++) {
                    // 判断数组中是否存在一个元素和 i 位置的值相等，flag代表是否存在
                    if (digits[j].equals(str.substring(i, i + 1))) {
                        flag = true;
                        break;
                    } else {
                        flag = false;
                    }
                }
            }
            // z 代表当前位数上，数组 digits 中比 i 位置的字符小的元素的数量
            int z = 0;
            for (int j = 0; j < length; j++) {
                if (Integer.parseInt(digits[j]) < Integer.parseInt(str.substring(i, i + 1))) {
                    z++;
                }
            }
            // 因为当前位数比 i 位置要小，所以后续可以直接全部随机
            for (int j = 0; j < str.length() - i - 1; j++) {
                z *= length;
            }
            count += z;
            // 如果存在所有数字都相等的值，那么 count++
            if (i == str.length() - 1 && flag) {
                count++;
            }
            // 如果数组 digits 中存在字符比 i 位置的字符要小，则直接计算
        }
        return count;
    }
}
